§1.1 Field of the Invention
The present invention concerns detecting errors in connections, such as multi-protocol label switching (MPLS) label-switched paths (LSPs).
§1.2 Description of Related Art
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art to the present invention. Although one skilled in the art will be familiar with networking, circuit switching, packet switching, and label-switched paths, each is briefly introduced below for the convenience of the reader less skilled in the art. More specifically, circuit-switched and packet-switched networks and the need for label-switched paths are introduced in §1.2.1. Then, label-switched path failures, some known failure responses, and their limitations are introduced in §1.2.2 below.
§1.2.1 Circuit-Switched Networks and Packet-Switched Networks, and the Need for Label-Switched Paths
Circuit-switched networks establish a connection between hosts (parties to a communication) for the duration of their communication. The public-switched telephone network (“PSTN”) is an example of a circuit-switched network, where parties to a call are provided with a connection for the duration of the call. Unfortunately, for communications of short, infrequent “bursts” of data between hosts, providing a connection for the duration of a call simply wastes communications resources when no data is being transferred. The desire to avoid such inefficiencies has lead to the development of packet-switched networks.
Packet-switched networks forward addressed data (referred to as “packets” in the specification below without loss of generality), typically on a best efforts basis, from a source to a destination. Many large packet-switched networks are made up of interconnected nodes (referred to as “routers” in the specification below without loss of generality). The routers may be geographically distributed throughout a region and connected by links (e.g., optical fiber, copper cable, wireless transmission channels, etc.). In such a network, each router typically interfaces with (e.g., terminates) multiple links.
Packets traverse the network by being forwarded from router to router until they reach their destinations (as typically specified by so-called layer-3 addresses in the packet headers). Routers exchange route information and develop forwarding information based on the route information. The forwarding information defines which output port is associated with a particular destination address or a portion of a destination address. Unlike switches, which establish a connection for the duration of a “call” or “session” and send data received on a given input port out on a given output port, routers typically examine the destination address of each packet and use the forwarding information to determine from the destination address the appropriate output port on which to send each packet.
In some cases, using known routing protocols (e.g., shortest path algorithms) to determine routes and forwarding information is becoming unacceptable in light of the ever-increasing volume of Internet traffic and the mission-critical nature of some Internet applications. Such known routing protocols can actually contribute to network congestion if they do not account for bandwidth availability and traffic characteristics when constructing routing and forwarding tables. To alleviate or avoid this problem, traffic flows can be mapped onto an existing physical topology, thereby moving traffic flows away from congested shortest paths to a less congested path. Alternatively, paths can be determined autonomously, even on demand. Label-switching can be used to establish a fixed path from a head-end node (e.g., an ingress router) to a tail-end node (e.g., an egress router). Once a path is determined, each router in the path may be configured manually or via some signaling mechanism to forward packets to a peer (e.g., a “downstream” neighbor) router in the path. Routers in the path determine that a given set of packets (e.g., a flow), are to be sent over the fixed path (as opposed to being routed individually) based on unique labels added to the packets.
The path generated may be an LSP. More specifically, the operations of forwarding a packet to a next hop based on address information can be thought of as two steps—partitioning the entire set of possible packets into a set of forwarding equivalence classes (FECs), and mapping each FEC to a next hop. As far as the forwarding decision is concerned, different packets which get mapped to the same FEC are indistinguishable. With MPLS, a packet is assigned to a particular FEC just once, as the packet enters the label-switched domain of the network. The FEC to which the packet is assigned is encoded as a label, typically a short, fixed length value. Thus, at subsequent nodes no further header analysis need be done—all subsequent forwarding over the label-switched domain is driven by the labels. FECs may be generalized such that particular ports, wavelengths, time slots, channels, etc. are used instead of, or encoded by, labels.
FIG. 1 illustrates an LSP 110 across a network. Notice that LSP 110 is simplex—traffic flows in one direction from a head-end label-switching router (LSR) 120 at an ingress edge through several LSRs to a tail-end LSR 130 at an egress edge. Generally, duplex traffic requires two LSPs—one for each direction. Notice also that LSP 110 is defined by the concatenation of one or more label-switched hops, allowing a packet to be forwarded from one LSR to another across the MPLS domain defined by LSP 110.
LSR 130 interprets the destination address of each unlabeled packet, performs a longest-match routing table lookup, maps the packet to an FEC, assigns a label to the packet based on the FEC, and forwards it to the next hop in the LSP. In the MPLS domain, the LSRs ignore the packet's network layer address and simply forward the packet using label-swapping. When the labeled packet arrives at the egress LSR, if the next hop is not an LSR the egress LSR discards (“pops”) the label and forwards the packet using conventional (e.g., longest-match IP) forwarding. Alternatively, a penultimate LSP can discard the label before the packet is forwarded to the egress LSR.
§1.2.2 “Failures” in a Label-Switched Path
As shown in FIG. 1, if a connection (link2) between two LSRs fails, traffic may be switched over to one or more “failover” links which may be an LSP itself. Some routers have “fast reroute” capabilities where a router upstream of a failed connection (e.g., a failed link, neighboring node, or interface) switches over to another connection while the ingress router determines a new LSP. The draft, “Fast Reroute Extensions to RSVP-TE for LSP Tunnels”, Ping Pan Ed., draft-ietf-mpls-rsvp-lsp-fastreroute-00.txt (the Internet Engineering Task Force January 2002) (referred to as “the fast reroute draft” and incorporated by reference) describes one fast reroute scheme. Although such fast reroute techniques facilitate fast switchover (e.g., on the order of msec) after a failed connection is detected, detecting the failed connection can take too long in many instances.
Some protocols for managing LSPs (such as the Resource Reservation Protocol-Traffic Engineering (RSVP-TE)) use so-called “neighbor hellos” to get adjacency information, but the period of the hellos is too long (e.g., one to three seconds) for some failover purposes. If the protocol waits to miss a few expected hellos before concluding that a connection is down, the time to detect a down connection can be ˜15 seconds. During this time, a lot of important data can be lost! The request for comments, “RSVP-TE: Extensions to RSVP for LSP Tunnels,” Awduche et al., Request for Comments: 3209 (the Internet Engineering Task Force December 2001) (incorporated by reference) describes RSVP-TE.
Although some hardware signaling techniques for checking connections exist (e.g., SONET Automatic Protection Switching (APS), data carrier connect, etc.), and such hardware signaling techniques may be fast, many shared media interfaces, such as Gigabit Ethernet for example, do not currently support hardware signaling. Accordingly, adjacencies or connections that use such interfaces cannot be checked quickly.